package com.lyj.sc.SecondBruchToReview.ListNode20220720;

import java.util.List;

/**
 * @program: code-random
 * @description: 链表复习
 * @author: lyj
 * @create: 2022-07-20 09:59
 * @version: 1.0
 * @Modifier By:
 **/
class ListNode{
    int val;
    ListNode next;
    ListNode(){};
    ListNode(int val){this.val=val;};
    ListNode(int val,ListNode next){
        this.val=val;
        this.next=next;
    }
}
public class Solution {
    //203. 移除链表节点
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyNode = new ListNode(-1,null);
        dummyNode.next=head;
        ListNode pre = dummyNode;
        ListNode current = head;
        while (current!=null){
            if(current.val==val){
                pre.next=current.next;
            }else {
                pre=current;
            }
            current=current.next;
        }
        return dummyNode.next;
    }
    //206. 反转链表
    public ListNode reverseList(ListNode head) {
        //虚拟头节点
        ListNode prev = null;
        ListNode cur = head;
        while (cur!=null){
            ListNode temp = cur.next;
            cur.next=prev;
            prev=cur;
            cur=temp;
        }
        return prev;
    }
    //24. 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode =  new ListNode(0);
        //设置虚拟节点
        dummyNode.next=head;
        ListNode current = dummyNode;
        while (current.next!=null && current.next.next!=null){
            ListNode temp1 = current.next;
            ListNode temp2 = current.next.next;
            current.next=temp2;
            temp1.next=temp2.next;
            temp2.next=temp1;
            current=temp1;
        }
        return dummyNode;
    }
    //19. 删除链表的倒数第N个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next=head;
        int count = len(head)-n;
        if(count<0){
            return null;
        }
        ListNode cur = dummyNode;
        for (int i = 0; i < count; i++) {
            cur=cur.next;
        }
        cur.next=cur.next.next;
        return dummyNode.next;
    }
    public int len(ListNode node){
        int count = 0;
        while (node!=null){
            count++;
            node=node.next;
        }
        return count;
    }
    // 面试题 02.07. 链表相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //curA curB 差值相减
        int curA = len(headA);
        int curB = len(headB);
        if(curA<curB){
            ListNode temp=headA;
            headA=headB;
            headB=temp;
            int te=curA;
            curA=curB;
            curB=te;
        }
        //差值
        int count =curA-curB;
        while (count>0){
            headA=headA.next;
            count--;
        }
        while (headB!=null&&headA!=null){
            if(headA==headB){
                return headA;
            }
            headA=headA.next;
            headB=headB.next;
        }
        return null;
    }
    // 142. 环形链表 II 快慢指针
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if (fast==slow){
                slow=head;
                while (slow!=fast){
                    slow=slow.next;
                    fast=fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}
/// TODO: 2022/7/20  没做出来
//707 设计链表
class MyLinkedList {
    public ListNode dummyNode;
    int count;

    public MyLinkedList() {
        this.dummyNode= new ListNode(0,null);
        this.count=0;
    }

    public int get(int index) {
        if(count<index||index>count){
            return -1;
        }
        ListNode node = dummyNode;
        for (int i = 0; i <= index; i++) {
            node=node.next;
        }
        return node.val;
    }

    public void addAtHead(int val) {
        count++;
        ListNode next = new ListNode(val,null);
        next.next=dummyNode.next;
        dummyNode.next=next;
    }

    public void addAtTail(int val) {
        count++;
        ListNode node = dummyNode;
        while (node.next!=null){
            node=node.next;
        }
        ListNode next = new ListNode(val,null);
        node.next=next;
    }

    public void addAtIndex(int index, int val) {
        if (index==count){
            count++;
            addAtTail(val);
            return;
        }
        if(index>count){
            return;
        }
        if(index<0){
            count++;
            addAtHead(val);
            return;
        }
        count++;
        ListNode node = dummyNode;
        ListNode next = new ListNode(val,null);
        for (int i = 0; i < index; i++) {
            node=node.next;
        }
        next.next=node.next;
        node.next=next;
    }

    public void deleteAtIndex(int index) {
        if(index>=count){
            return;
        }
        if (index<0){
            return;
        }
        ListNode node = dummyNode;
        for (int i = 0; i < index; i++) {
            node=node.next;
        }
        node.next=node.next.next;
        count--;
    }
}


